package com.algorithm.connectivity;

/**
 * 快速查找连通算法
 * 算法复杂度：O(n2) 平方级的时间复杂度
 */
public class QuickFindUF {

    private int[] ids;

    public QuickFindUF(int N){
        ids=new int[N];
        for(int i=0;i<N;i++){
            ids[i]=i;
        }
    }
    //连通性判断
    public boolean connected(int p,int q){
        return ids[p] == ids[q];
    }

    //连通p和q（此处前置条件为q,p小于N）
    public void union(int q,int p){
        int pid=ids[p];
        int qid=ids[q];
        for(int i=0;i<ids.length;i++){
            if(ids[i] == pid){
               ids[i]=qid;
            }
        }
    }

}
